package com.example.dynamicplanning;

/**
 * @author wxz
 * <p>
 * 1143. 最长公共子序列
 * 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * <p>
 * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * <p>
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 * 示例 2：
 * <p>
 * 输入：text1 = "abc", text2 = "abc"
 * 输出：3
 * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 * <p>
 * <p>
 * 思路：
 * 1. 状态定义
 * 比如对于本题而言，可以定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。 （注：text1[0:i-1] 表示的是 text1 的 第 0 个元素到第 i - 1 个元素，两端都包含）
 * 之所以 dp[i][j] 的定义不是 text1[0:i] 和 text2[0:j] ，是为了方便当 i = 0 或者 j = 0 的时候，dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为 0.
 * <p>
 * 2. 状态转移方程
 * 知道状态定义之后，我们开始写状态转移方程。
 * <p>
 * 当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 c 的最长公共子序列长度 0 + 1 = 1。
 * 当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值，即 1。
 * 综上状态转移方程为：
 * <p>
 * dp[i][j] = dp[i - 1][j - 1] + 1dp[i][j]=dp[i−1][j−1]+1, 当 text1[i - 1] == text2[j - 1];text1[i−1]==text2[j−1];
 * dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])dp[i][j]=max(dp[i−1][j],dp[i][j−1]), 当 text1[i - 1] != text2[j - 1]text1[i−1]!=text2[j−1]
 * 3. 状态的初始化
 * 初始化就是要看当 i = 0 与 j = 0 时， dp[i][j] 应该取值为多少。
 * <p>
 * 当 i = 0 时，dp[0][j] 表示的是 text1text1 中取空字符串 跟 text2text2 的最长公共子序列，结果肯定为 0.
 * 当 j = 0 时，dp[i][0] 表示的是 text2text2 中取空字符串 跟 text1text1 的最长公共子序列，结果肯定为 0.
 * 综上，当 i = 0 或者 j = 0 时，dp[i][j] 初始化为 0.
 * <p>
 * 4. 遍历方向与范围
 * 由于 dp[i][j] 依赖与 dp[i - 1][j - 1] , dp[i - 1][j], dp[i][j - 1]，所以 ii 和 jj 的遍历顺序肯定是从小到大的。
 * 另外，由于当 ii 和 jj 取值为 0 的时候，dp[i][j] = 0，而 dp 数组本身初始化就是为 0，所以，直接让 ii 和 jj 从 1 开始遍历。遍历的结束应该是字符串的长度为 len(text1)len(text1) 和 len(text2)len(text2)。
 * <p>
 * 5. 最终返回结果
 * 由于 dp[i][j] 的含义是 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。我们最终希望求的是 text1 和 text2 的最长公共子序列。所以需要返回的结果是 i = len(text1) 并且 j = len(text2) 时的 dp[len(text1)][len(text2)]。
 * 所以返回的事dp[m][n]
 * <p>
 * ⚠️此题设定"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 这个解法的巧妙就在于每一层的递归只取前面的的结果。也就是可以自动排除错序的这种情况。
 * 因为错序的数字，在未遍历和已遍历中，而不会同时出现在同一方向
 */
public class LongestCommonSubsequence {
    public static void main(String[] args) {
        LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
        String text1 = "aecde";
        String text2 = "ace";
        System.out.println(longestCommonSubsequence.longestCommonSubsequence(text1, text2));
        System.out.println(longestCommonSubsequence.maxUncrossedLines(new int[]{1, 4, 2}, new int[]{1, 2, 4}));
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 1035. 不相交的线
     * 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
     * <p>
     * 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
     * <p>
     * nums1[i] == nums2[j]
     * 且绘制的直线不与任何其他连线（非水平线）相交。
     * 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
     * <p>
     * 以这种方法绘制线条，并返回可以绘制的最大连线数。
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：nums1 = [1,4,2], nums2 = [1,2,4]
     * 输出：2
     * 解释：可以画出两条不交叉的线，如上图所示。
     * 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
     * <p>
     * 思路：与1143一摸一样，既然要找最多的不相交线的个数，也就是要找最长不连续公共子序列个数
     * 我的版本，之前出问题主要是初始化的时候出了问题。 其实初始化的时候后面的值至少应该
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            boolean flag = nums1[i] == nums2[0];
            while (i < m && flag) {
                dp[i][0] = 1;
                i++;
            }
        }
        for (int i = 0; i < n; i++) {
            boolean flag = nums1[0] == nums2[i];
            while (i < n && flag) {
                dp[0][i] = 1;
                i++;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }


    /**
     * 583. 两个字符串的删除操作
     * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
     * <p>
     * 示例：
     * <p>
     * 输入: "sea", "eat"
     * 输出: 2
     * 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
     * <p>
     * 思路：1143变种题
     * 将两个字符串变为相等的，本质上是求两个字符串的 最长公共子序列  的长度
     * 求出这个长度后，用两个字符串长度分别减去公共长度即为需要进行操作的次数。
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int lcs = dp[m][n];
        return m - lcs + n - lcs;
    }
}

/**
 * 72. 编辑距离 -hard
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 *
 * 示例 1：
 *
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * 思路：此题与两个字符串的删除操作的区别是只允许改变一个字符，所以不能单纯的用公共序列去做
 */
class MinDistance {

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        //dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 因为dp数组有效位从1开始
                // 所以当前遍历到的字符串的位置为i-1 | j-1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
